package pers.vic.practice;

import java.net.URL;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.List;

/**
 * 描述: 找两个字符串的最长公共子串
 * <p>
 *     找两个字符串的最长公共子串。如果字符串一的所有字符按其在
 *     字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符
 *    串二的子串。注意，并不要求子串（字符串一）的字符必须连续出现
 *    在字符串二中。请编写一个程序，从文件读入两个字符串，求它们的
 *    最长公共子串，并打印出最长公共子串。
 * 输入：两个文本文件，每个文件中字符长度应大于 100 字节
 * https://alchemist-al.com/algorithms/longest-common-subsequence
 * </p>
 * @author Vic.xu
 * @date 2022-04-02 15:41
 */
public class LongestCommonString {

    /**
     * 应该先计算出最长公共序列，然后回溯出最长公共字符串
     * 初看到这个问题，就感觉应该是一个典型的动态规划问题。
     * 按照我的理解，动态规划有三个部分
     * 1. 找出状态的定义，动态规划类似递归或递推，利用历史状态推出新的状态。这个状态的定义往往是最困难的
     * 2. 定义好状态之后，就是要找出关系，这个关系，或者说是状态转移也是比较复杂的，需要多方考虑
     * 3.定义好状态的初始值，因为一切状态都是从初始状态变化而来
     *
     * 那关于本题：
     * 1. 如何定义状态：
     *  一个二维数组arr[len+1][len2+1], 其中的arr[i][j]表示字符串1的[0,i]和字符串2的[0,j]的最长公共序列长度
     * 2. 初始状态是什么：即第一行和空匹配的最长公共序列是0；第一列和空匹配的最长公共序列也是0
     * 3状态的转移：
     *  3.1 行字符串[i]位置字符和和列字符串[j]位置的匹配情况:
     *  3.2 当不匹配的时候，则到[i,j]位置最长的序列为前一行或前一列的最长序列
     *  3.3 当匹配的时候，则[i,j]位置最长的序列为[i-i][j-1]的基础上加1
     *
     */

    public static void longestCommonString(String s1, String s2) {
        if (!otherCheck(s1, s2)) {
            return;
        }
        int row = s1.length();
        int col = s2.length();
        //1. 定义二维数组，其中sequences[i][j]表示到s1的第i个字符和到s2的第j个字符最长公共序列长度
        int[][] sequences = new int[row + 1][col + 1];
        //2. 定义初始状态:第一行和第一列和空匹配的最长公共序列长度均为0，由于java初始化的时候默认为0，略过赋值
        for (int i = 1; i <= row; i++) {
            //行中第i和字符
            char rc = s1.charAt(i - 1);
            for (int j = 1; j <= col; j++) {
                //列中的第j个字符
                char cc = s2.charAt(j - 1);

                if (rc == cc) {
                    //如果匹配，则在各自的上一个字符的基础上+1即可
                    sequences[i][j] = sequences[i - 1][j - 1] + 1;
                } else {
                    //如果不匹配，则在当前行字符和列字符的上一个字符中取最大的匹配序列即可
                    sequences[i][j] = Math.max(sequences[i - 1][j], sequences[i][j - 1]);
                }
            }
        }
        System.out.println("最长公共子串的长度是" + sequences[row][col]);
        //输出子串
       char[] common = new char[sequences[row][col]];
        int index = common.length - 1;
        int i = row - 1, j = col - 1;
        while (index >= 0) {
            if (i > 0 && sequences[i][j] == sequences[i - 1][j]) {
                //向左移动
                i--;
            } else if (j > 0 && sequences[i][j] == sequences[1][j - 1]) {
                //向上移动
                j--;
            } else {
                //向左上方移动
                common[index--] = s1.charAt(i);
                j--;
                i--;
            }
        }
        String sub = String.valueOf(common);
        System.out.println("最长公共子串是:\n" + sub);
    }

    private static boolean otherCheck(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() == 0 | s2.length() == 0) {
            System.out.println("没有公共子串");
            return false;
        }
        if (s1.contains(s2)) {
            System.out.println("最长公共序列为" + s2.length());
            System.out.println("最长公共子串为" + s2);
            return false;
        }
        if (s2.contains(s1)) {
            System.out.println("最长公共序列为" + s1.length());
            System.out.println("最长公共子串为" + s1);
            return false;
        }
        return true;
    }

    /**
     * 读取resources下文件中的内容
     * @param filePath 文件路径
     * @return 全部字符串
     * @throws Exception ex
     */
    private static String readFile(String filePath) throws Exception {
        URL resource = LongestCommonString.class.getClassLoader().getResource(filePath);
        assert resource != null;
        List<String> lines = Files.readAllLines(Paths.get(resource.toURI()), StandardCharsets.UTF_8);
        return String.join("", lines);
    }

    public static void main(String[] args) throws Exception {
        String s1 = readFile("f1.txt");
        String s2 = readFile("f2.txt");
        System.out.println(s1 + "\n-->字符串1总长度：" + s1.length() );
        System.out.println(s2 + "\n-->字符串2总长度：" + s2.length() );
        longestCommonString(s1, s2);


    }
}


//https://blog.csdn.net/chenhuanjing/article/details/108760657?spm=1001.2101.3001.6650.6&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7ERate-6.pc_relevant_paycolumn_v3&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7ERate-6.pc_relevant_paycolumn_v3&utm_relevant_index=10
